1. Field of the Invention
The present invention relates to contact shape computing apparatuses and methods and computer programs therefor for detecting contact between a plurality of three-dimensional solid models and computing a contact shape between two solid bodies in contact with each other. More particularly, the present invention relates to a contact shape computing apparatus and method and a computer program therefor for completely and quickly computing a contact polygon between two solid bodies in collision or in contact with each other.
2. Description of the Related Art
Recently, research and development of the structure and stable walking control of legged mobile robots has made advances, and expectations on the practical use of such legged mobile robots have increased. Such legged mobile robots are less stable and have greater difficulty in posture control and walk control than crawler robots, but the legged mobile robots are advantageous in that they can realize flexible walking and running motions such as moving up and downstairs and leaping over obstacles. Proposals have been made for, for example, humanoid robots that have legs serving as moving means and that can generate stable motion patterns in real time for moving from a contact state to a non-contact state.
In many cases, it is necessary for this type of mobile robot to determine a “contact polygon”, which is the shape of a region where objects or an object and the robot exert force on each other. With a dynamic simulation representing on a computer physical interactions such as collisions or contacts among a plurality of objects coexisting in a virtual environment, it is necessary to detect a collision occurring between solid bodies and to detect the contact state between the solid bodies, thereby applying an appropriate reaction force to the point of collision.
The zero moment point (ZMP) is employed as a criterion for determining the stability in posture control of legged mobile robots. The ZMP is a point on the floor where the moment due to the floor reaction force is zero (e.g., see Miomir Vukobratovic, “Legged Locomotion Robots” (Ichiro Kato et al., “Hoko robotto to jinkou no ashi (Walking Robots and Artificial Legs)”, published by Nikkan Kogyo Shimbun, Ltd.)). If it is possible to conclude, on the basis of the mechanical deduction based on the “d'Alembert's principle” stating that the gravitational and inertial forces acting from the walking system to the floor and their moments are counterbalanced by the floor reaction force serving as the reaction force acting from the floor to the walking system and the floor reaction moment, that the ZMP resides inside a support polygon formed by a sole contact point and the floor, the dynamic consistency of the corresponding motion pattern is ensured. Thus, the posture becomes stable (see. FIG. 19). The posture of the robot becomes more stable when the support polygon corresponding to the posture is larger.
The support polygon is the convex hull, which is the smallest convex polygon including a set of all contact points between the legged robot and the plane floor, and is a concept similar to a contact polygon in collision detection algorithms. In other words, the contact polygon can be applied to the control of legged robots. If the accurate contact polygon between the sole and the floor can be quickly detected, the support polygon can be formed in real time, thereby stabilizing the motion of the legged robot on the floor.
The contact polygon is not limited to a ground polygon on the plane floor. As shown in FIG. 20, when the robot is simultaneously in contact with a plurality of planes with different normal vectors or when the robot is in physical contact with itself (self-interference), it is necessary to accurately detect the contact state to perform more general stabilization and to arrange a complicated motion plan.
For example, as shown in FIG. 21, when two cubes are in contact with each other, it is necessary to apply a reaction force to the vertices A, B, C, and D defining a contact shape. When two solid bodies are in contact with each other, the shape of the contact portion between the two solid bodies, such as the figure ABCD, serves as the contact polygon.
However, many of the known collision detection algorithms can obtain only some of the collision points between two solid bodies and are unable to completely compute the contact polygon. For example, as shown in FIG. 22, the known collision detection algorithms can obtain only one representative point P per collision (which is generally the most penetrating point or the closest point) or, as shown in FIG. 23, a triangular mesh M where the contact is occurring.
Inconvenience is caused when a dynamic simulation is performed directly using the result of an insufficient collision detection algorithm. The case where a cube is placed on a flat floor is examined by way of example. For example, as shown in FIGS. 24A and 24B, in the case where a reaction force is applied only to a representative point P, if the floor reaction force model has no resilience, as shown in FIG. 24A, the cube rotates around the point P and a point Q opposite the point P gradually penetrates through the floor since the point Q is not supported. When the simulation advances one frame, the point Q becomes the most penetrating point, and, instead of the point P, the reaction force is applied to the point Q. As a result, the cube rotates around the point Q, and, this time, the point P penetrates further through the floor. When such situations repeatedly occur, the cube penetrates through the floor without limit. If the floor reaction force model has resilience, as shown in FIG. 24B, although the penetration does not become greater than or equal to a certain amount, the point of application switches between the point P and the point Q, thereby generating vibrations. It is thus difficult to achieve satisfactory simulation results.
The inventors of the present invention consider that such a problem can be solved by computing a perfect contact polygon and applying a reaction force to a group of vertices of the contact polygon. As a method of computing a contact polygon, there is a method of obtaining the intersection between two solid bodies interfering with each other. For example, proposals have been made for a method of computing a reaction force based on the intersection between two solid bodies (for example, see “Rikikaku interaction no tame no tamentai no sesshokutaiseki ni motozuku jitsujikan goutai undou simulation (Real-Time Rigid-Body Motion Simulation based on Contact Volume of Polyhedra for Sense-of-Force Simulation)”, The Transactions of the Society of Instrument and Control Engineers, Vol. 40, No. 2, 2004). Also, proposals have been made for a method of computing the intersection between convex solid bodies (for example, see D. E. Muller and F. P. Preparata, “Finding the Intersection of Two Convex Polyhedra”, Theoretical Computer Science 7(2), pp. 217-236, 1987, and S. Hertel, K. Mehlhorn, M. Mantyla and J. Nievergelt, “Space Sweep Solves Intersection of Two Convex Polyhedra Elegantly”, Acta Informatica 21, pp. 501-519, 1984).
However, all of the above methods perform calculations using all the vertices of two solid bodies interfering with each other, thus involving a large number of calculations. If the shape becomes more complex or the number of objects increases, it may be difficult to perform a simulation in real time.